import collections
class Solution(object):
    def numSquarefulPerms(self, nums):
        n = len(nums)
        c = collections.Counter(nums)
        st = []
        self.ans = 0
        def dfs(k):
            if k == n:
                self.ans += 1
            for key in c:
                if c[key] > 0:
                    if not st:
                        st.append(key)
                        c[key] -= 1
                        dfs(k + 1)
                        st.pop()
                        c[key] += 1
                    else:
                        val = key + st[-1]
                        if int(val ** 0.5) ** 2 == val:
                            st.append(key)
                            c[key] -= 1
                            dfs(k + 1)
                            st.pop()
                            c[key] += 1
        dfs(0)
        return self.ans




data = Solution()
nums = [1, 17, 8]
print(data.numSquarefulPerms(nums))